package com.jacklei.ch04;

import javax.swing.plaf.nimbus.NimbusLookAndFeel;
import java.util.Stack;

/*
* 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 

示例 1：


输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：


输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]
 

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class ReverseLinkedList {
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(3);
        ReverseLinkedList r = new ReverseLinkedList();
        ListNode node = r.reverseList2(list1);
        while (node != null){
            System.out.println(node.val);
            node =node.next;
        }
    }
    //递归法
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
    //指针法
    public ListNode reverseList1(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode per = head;
        ListNode after = head.next;
        per.next = null;
        while(per != null && after != null){
            ListNode p = after.next;
            after.next = per;
            per = after;
            after = p ;
        }
        return per;
    }
    //使用额外的数据结构
    public ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null) return head;
        Stack<ListNode> stack = new Stack<>();
        while (head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode newHead = stack.pop();
        ListNode cur = newHead;
        while (!stack.isEmpty()){
            ListNode pop = stack.pop();
            pop.next = null;
            cur.next = pop;
            cur = cur.next;

        }
        cur = null;
        return newHead;
    }
}
